package com.xj.algorithm.leetcode;

/**
 * 排列硬币
 */
public class L441_硬币排列梯形的高度 {

    /**
     * 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
     *
     * 给定一个数字 n，找出可形成完整阶梯行的总行数。
     *
     * n 是一个非负整数，并且在32位有符号整型的范围内。
     *
     * 示例 1:
     *
     * n = 5
     *
     * 硬币可排列成以下几行:
     * ¤
     * ¤ ¤
     * ¤ ¤
     *
     * 因为第三行不完整，所以返回2.
     * 示例 2:
     *
     * n = 8
     *
     * 硬币可排列成以下几行:
     * ¤
     * ¤ ¤
     * ¤ ¤ ¤
     * ¤ ¤
     *
     * 因为第四行不完整，所以返回3.
     */
    public static void main(String[] args) {
        System.out.println(arrangeCoins(5));
        System.out.println(arrangeCoins(8));
        System.out.println(arrangeCoins(1804289383));

        System.out.println(arrangeCoinsGood(5));
        System.out.println(arrangeCoinsGood(8));
        System.out.println(arrangeCoinsGood(1804289383));
    }

    //自己的解法：本质是等差数列求和的范围,注意乘法数组越界
    public static int arrangeCoins(int n) {
        int level=1;
        while (level<=n){
            n-=level;
            level++;
        }
        return --level;
    }

    //精彩解法：一元二次求根公式，注意越界
    public static int arrangeCoinsGood(int n) {
        return (int)(Math.sqrt(2) * Math.sqrt(n + 0.125) - 0.5);
    }
}
